package a_doubleWrite;

import java.util.ArrayList;
import java.util.List;

/**
 * 986. 区间列表的交集
 * 给定两个由一些 闭区间 组成的列表，firstList 和 secondList ，
 * 其中 firstList[i] = [starti, endi] 而 secondList[j] = [startj, endj] 。
 * 每个区间列表都是成对 不相交 的，并且 已经排序 。
 * <p>
 * 返回这 两个区间列表的交集 。
 *
 * @author: luolidong
 * @create: 2021-07-23 09:16
 * @version: 1.0
 */
public class L986 {
    public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
        if (firstList.length == 0 && secondList.length == 0) return new int[0][];
        if (firstList.length == 0) return secondList;
        if (secondList.length == 0) return firstList;

        //firstList = [[0,5],[5,10],[13,23],[24,25]],
        //secondList =[[1,5],[8,12],[15,24],[25,26]]

        List<int[]> list = new ArrayList<>();
        int a = 0;
        int b = 0;
        while (firstList.length > a && secondList.length > b) {
            int leftBound = Math.max(firstList[a][0], secondList[b][0]);
            int rightBound = Math.min(firstList[a][1], secondList[b][1]);
            if (leftBound <= rightBound) {
                list.add(new int[]{leftBound, rightBound});
            }
            //判断哪个需要右移，右边数较小的右移
            if (firstList[a][1] < secondList[b][1]) {
                a++;
            } else {
                b++;
            }
        }
        return list.toArray(new int[list.size()][]);
    }
}
